HOME

TheInfoList



OR:

In
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
, an area of mathematics, graph enumeration describes a class of
combinatorial enumeration Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infin ...
problems in which one must count
undirected In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ...
or
directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pai ...
s of certain types, typically as a function of the number of vertices of the graph. These problems may be solved either exactly (as an
algebraic enumeration Algebraic enumeration is a subfield of enumeration that deals with finding exact formulas for the number of combinatorial objects of a given type, rather than estimating this number asymptotically. Methods of finding these formulas include generati ...
problem) or
asymptotically In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related contexts, ...
. The pioneers in this area of mathematics were
George Pólya George Pólya (; hu, Pólya György, ; December 13, 1887 – September 7, 1985) was a Hungarian mathematician. He was a professor of mathematics from 1914 to 1940 at ETH Zürich and from 1940 to 1953 at Stanford University. He made fundamenta ...
,
Arthur Cayley Arthur Cayley (; 16 August 1821 – 26 January 1895) was a prolific British mathematician who worked mostly on algebra. He helped found the modern British school of pure mathematics. As a child, Cayley enjoyed solving complex maths problems ...
and J. Howard Redfield.


Labeled vs unlabeled problems

In some graphical enumeration problems, the vertices of the graph are considered to be ''labeled'' in such a way as to be distinguishable from each other, while in other problems any permutation of the vertices is considered to form the same graph, so the vertices are considered identical or ''unlabeled''. In general, labeled problems tend to be easier. As with combinatorial enumeration more generally, the
Pólya enumeration theorem The Pólya enumeration theorem, also known as the Redfield–Pólya theorem and Pólya counting, is a theorem in combinatorics that both follows from and ultimately generalizes Burnside's lemma on the number of orbits of a group action on a set. ...
is an important tool for reducing unlabeled problems to labeled ones: each unlabeled class is considered as a symmetry class of labeled objects.


Exact enumeration formulas

Some important results in this area include the following. *The number of labeled ''n''-vertex simple undirected graphs is 2''n''(''n'' −1)/2. *The number of labeled ''n''-vertex
simple directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pair ...
s is 2''n''(''n'' −1). *The number ''Cn'' of connected labeled ''n''-vertex undirected graphs satisfies the
recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a paramete ...
::C_n=2^ - \frac\sum_^ k 2^ C_k. :from which one may easily calculate, for ''n'' = 1, 2, 3, ..., that the values for ''Cn'' are ::1, 1, 4, 38, 728, 26704, 1866256, ... *The number of labeled ''n''-vertex free trees is ''n''''n''−2 (
Cayley's formula In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer n, the number of trees on n labeled vertices is n^. The formula equivalently counts the number of spanning trees ...
). *The number of unlabeled ''n''-vertex
caterpillars Caterpillars ( ) are the larval stage of members of the order Lepidoptera (the insect order comprising butterflies and moths). As with most common names, the application of the word is arbitrary, since the larvae of sawflies (suborder Sy ...
is. ::2^+2^.


Graph database

Various research groups have provided searchable database that lists graphs with certain properties of a small sizes. For example
The House of Graphs

Small Graph Database


References

{{reflist, 2 Enumerative combinatorics